#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        vector<int>ups(nums.size(), 0);
        vector<int>downs(nums.size(), 0);
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j])
                    ups[i] = max(ups[i], downs[j] + 1);
                else if (nums[i] < nums[j])
                    downs[i] = max(downs[i], ups[j] + 1);
            }
        }
        return max(ups.back(), downs.back()) + 1;
    }
};